Introduction

Gaussian elimination is a systematic method for solving systems of linear equations.
Because you already know what a system of equations is, our goal here is to show you how to turn any system into a simpler one that is easy to solve.

Gaussian elimination works by transforming a system step-by-step until the answer becomes obvious.

Why Gaussian Elimination Works

• Every system of linear equations can be rewritten in matrix form.
• We apply simple operations that do not change the solution:
  • Swap two rows.
  • Multiply a row by a nonzero number.
  • Add a multiple of one row to another row.
• These operations gradually simplify the system until it reaches a form where the solution is clear.

These operations are called row operations, and they preserve the solution set.

The Algorithm Step-by-Step

Here is the standard procedure:

1. Write the augmented matrix

For a system like
$2x + y = 5$
$x - y = 1$
we write $$\left[ \begin{array}{cc|c} 2 & 1 & 5 \\\\ 1 & -1 & 1 \end{array} \right]$$

2. Create a leading 1 in the first row

• If the first entry is not 1, divide the row by its first number.
• If the first entry is 0, swap with a row below it.

3. Use the leading 1 to eliminate entries below it

• Make all numbers below the leading 1 into 0 by adding/subtracting multiples of the first row.

4. Move to the next row and repeat

• Find the next column with a nonzero entry.
• Create a leading 1.
• Eliminate entries below it.

5. Continue until the matrix is in row-echelon form

Row-echelon form looks like:

• All leading entries (pivots) move to the right as you go down.
• All-zero rows (if any) are at the bottom.
• All entries below each leading 1 are zero.

6. Back-substitute

Once the matrix is simple enough, convert it back into equations and solve from bottom to top.

A Fully Worked Example

Solve the system: $$\begin{aligned} x + y + z &= 6 \\\\ 2x - y + 3z &= 14 \\\\ - x + 2y - z &= -2 \end{aligned}$$

Step 1: Augmented matrix

$$\left[ \begin{array}{ccc|c} 1 & 1 & 1 & 6 \\\\ 2 & -1 & 3 & 14 \\\\ -1 & 2 & -1 & -2 \end{array} \right]$$

Step 2: Eliminate below the first row

• Row2 → Row2 − 2·Row1
• Row3 → Row3 + Row1

Result: $$\left[ \begin{array}{ccc|c} 1 & 1 & 1 & 6 \\\\ 0 & -3 & 1 & 2 \\\\ 0 & 3 & 0 & 4 \end{array} \right]$$

Step 3: Create a leading 1 in Row2

Divide Row2 by $-3$: $$\left[ \begin{array}{ccc|c} 1 & 1 & 1 & 6 \\\\ 0 & 1 & -\tfrac{1}{3} & -\tfrac{2}{3} \\\\ 0 & 3 & 0 & 4 \end{array} \right]$$

Step 4: Eliminate below Row2

Row3 → Row3 − 3·Row2: $$\left[ \begin{array}{ccc|c} 1 & 1 & 1 & 6 \\\\ 0 & 1 & -\tfrac{1}{3} & -\tfrac{2}{3} \\\\ 0 & 0 & 1 & 6 \end{array} \right]$$

Step 5: Back-substitute

From Row3: $z = 6$

From Row2:

• $y - \tfrac{1}{3}z = -\tfrac{2}{3}$
• $y - 2 = -\tfrac{2}{3}$
• $y = \tfrac{4}{3}$

From Row1:

• $x + y + z = 6$
• $x + \tfrac{4}{3} + 6 = 6$
• $x = -\tfrac{4}{3}$

Solution

$$(x, y, z) = \left(-\tfrac{4}{3},\ \tfrac{4}{3},\ 6\right)$$

Common Pitfalls

• Forgetting to apply a row operation to every entry in the row.
• Mixing up which row is being replaced.
• Forgetting that multiplying a row by 0 is not allowed.
• Stopping too early before the matrix is simple enough to read the solution.

Exercises

1. Solve the system using Gaussian elimination:
   $x + y = 5$
   $2x - y = 1$

   Solution

   Solving:
   $x + y = 5$
   $2x - y = 1$
   Add the equations: $3x = 6$ → $x = 2$
   Then $y = 3$
   Solution: $(2,3)$

2. Put the following system into an augmented matrix:
   $3x - y + 2z = 7$
   $x + 4y - z = 1$

   Solution

   Augmented matrix: $$\left[ \begin{array}{ccc|c} 3 & -1 & 2 & 7 \\\\ 1 & 4 & -1 & 1 \end{array} \right]$$

3. Perform the row operation: Row2 → Row2 − 3·Row1 on $$\left[ \begin{array}{cc|c} 1 & 2 & 4 \\\\ 3 & -1 & 5 \end{array} \right]$$

   Solution

   Row2 − 3·Row1 gives: $$\left[ \begin{array}{cc|c} 1 & 2 & 4 \\\\ 0 & -7 & -7 \end{array} \right]$$

4. Solve the system:
   $x + 2y + z = 4$
   $2x + y - z = 1$
   $3x + 3y + z = 7$

   Solution

   After elimination, the solution is: $$(x, y, z) = (1, 1, 1)$$

5. True or false: Row operations can change the solution to a system.

   Solution

   False.
   Row operations never change the solution set.

6. Convert the matrix to row-echelon form: $$\left[ \begin{array}{cc|c} 2 & 4 & 6 \\\\ 1 & 3 & 5 \end{array} \right]$$

   Solution

   Swap rows to get a leading 1: $$\left[ \begin{array}{cc|c} 1 & 3 & 5 \\\\ 2 & 4 & 6 \end{array} \right]$$ Then Row2 → Row2 − 2·Row1: $$\left[ \begin{array}{cc|c} 1 & 3 & 5 \\\\ 0 & -2 & -4 \end{array} \right]$$ This is row-echelon form.